package com.ry.day1129;

import java.util.Arrays;

//和背包问题4差不多
public class LC740 {
    static class Solution {
        /**
         * @param amount: a total amount of money amount
         * @param coins: the denomination of each coin
         * @return: the number of combinations that make up the amount
         */
        public int change(int amount, int[] coins) {
            return shacache(amount,coins); //傻缓存
        }

        public int shacache(int amount,int[] coins){
            int n= coins.length;
            int[][] dp  = new int[n+1][amount+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }

            return f1(coins,0,amount,dp);
        }

        public int f1(int[] coins,int idx,int rest,int[][] dp){
            if(rest <0) return -1;
            if(idx == coins.length)
                return rest==0?1:0;

            if(dp[idx][rest] !=-1)
                return dp[idx][rest];

            int ans =0;
            for (int zhang = 0; zhang*coins[idx] <=rest ; zhang++) {
                int next= f1(coins,idx+1,rest-zhang*coins[idx],dp);
                if(next!=-1){
                    ans+=next;
                }
            }
            dp[idx][rest] =ans;
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj= new Solution();
        System.out.println(obj.change(10,new int[]{10}));
        System.out.println(obj.change(8,new int[]{2,3,8}));
    }
}
